//给你一个大小为 n 的 非负 整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。 
//
// 在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。 
//
// 返回使整个数组变为 0 所需的最少操作次数。 一个 
//子数组 是数组中的一段连续元素。
//
// 
//
// 示例 1： 
//
// 
// 输入: nums = [0,2] 
// 
//
// 输出: 1 
//
// 解释: 
//
// 
// 选择子数组 [1,1]（即 [2]），其中最小的非负整数是 2。将所有 2 设为 0，结果为 [0,0]。 
// 因此，所需的最少操作次数为 1。 
// 
//
// 示例 2： 
//
// 
// 输入: nums = [3,1,2,1] 
// 
//
// 输出: 3 
//
// 解释: 
//
// 
// 选择子数组 [1,3]（即 [1,2,1]），最小非负整数是 1。将所有 1 设为 0，结果为 [3,0,2,0]。 
// 选择子数组 [2,2]（即 [2]），将 2 设为 0，结果为 [3,0,0,0]。 
// 选择子数组 [0,0]（即 [3]），将 3 设为 0，结果为 [0,0,0,0]。 
// 因此，最少操作次数为 3。 
// 
//
// 示例 3： 
//
// 
// 输入: nums = [1,2,1,2,1,2] 
// 
//
// 输出: 4 
//
// 解释: 
//
// 
// 选择子数组 [0,5]（即 [1,2,1,2,1,2]），最小非负整数是 1。将所有 1 设为 0，结果为 [0,2,0,2,0,2]。 
// 选择子数组 [1,1]（即 [2]），将 2 设为 0，结果为 [0,0,0,2,0,2]。 
// 选择子数组 [3,3]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,2]。 
// 选择子数组 [5,5]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,0]。 
// 因此，最少操作次数为 4。 
// 
//
// 
//
// 提示: 
//
// 
// 1 <= n == nums.length <= 10⁵ 
// 0 <= nums[i] <= 10⁵ 
// 
//
// Related Topics 栈 贪心 数组 哈希表 单调栈 👍 21 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-11-10 00:04:30
 * @description 3542.将所有元素变为 0 的最少操作次数
 */
public class MinimumOperationsToConvertAllElementsToZero{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MinimumOperationsToConvertAllElementsToZero fun=new MinimumOperationsToConvertAllElementsToZero();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 子数组连续，只要前后不为0，中间有非0，就需要操作
	// 所以就是统计非0段的数量
	// 因为每次操作后，最小的非负整数会被置为0，所以挑选的段如果有0，就会被分割成多段，否则会循环选0

	// 首先通过观察发现：
	//
	//规律一：把若干相同的最小值同时变为 0，可以节省操作次数。
	//规律二：如果两个相同的数之间有更小的数，则他们一定不同一起被变为 0。
	//我们遍历数组，维护一个单调递增栈，表示当前递增的非零元素序列。
	//
	// 对于每个元素 a，如果栈顶元素大于 a，
	// 根据规律二，栈顶元素不可能和之后的元素一起操作，需要弹出栈顶。
	// 如果 a 已经为 0，跳过，因为已经不需要操作。
	// 如果栈为空或栈顶元素小于 a，说明我们需要新的一次操作来覆盖 a，并把它加入栈，并把操作次数加一。
	//
	//最后返回所有的操作次数。

	public int minOperations(int[] nums) {
		List<Integer> s = new ArrayList<>();
		int res = 0;
		for (int a : nums) {
			while (!s.isEmpty() && s.get(s.size() - 1) > a) {
				s.remove(s.size() - 1);
			}
			if (a == 0) continue;
			if (s.isEmpty() || s.get(s.size() - 1) < a) {
				res++;
				s.add(a);
			}
		}
		return res;
	}

	/*从左往右遍历数组，只在「必须要操作」的时候，才把答案加一。

什么时候必须要操作？

示例 3 nums=[1,2,1,2,1,2]，因为 2 左右两侧都有小于 2 的数，需要单独操作。

又例如 nums=[1,2,3,2,1]：

遍历到第二个 2 时，可以知道 3 左右两侧都有小于 3 的数，所以 3 必须要操作一次，答案加一。注意这不表示第一次操作的是 3，而是某次操作会把 3 变成 0。
遍历到末尾 1 时，可以知道中间的两个 2，左边有 1，右边也有 1，必须操作一次，答案加一。比如选择 [2,3,2] 可以把这两个 2 都变成 0。
最后，数组中的 1 需要操作一次都变成 0。
我们怎么知道「3 左右两侧都有小于 3 的数」？

遍历数组的同时，把遍历过的元素用栈记录：

如果当前元素比栈顶大（或者栈为空），那么直接入栈。
如果当前元素比栈顶小，那么对于栈顶来说，左边（栈顶倒数第二个数）比栈顶小（原因后面解释），右边（当前元素）也比栈顶小，所以栈顶必须操作一次。然后弹出栈顶。
如果当前元素等于栈顶，可以在同一次操作中把当前元素与栈顶都变成 0，所以无需入栈。注意这保证了栈中没有重复元素。
如果当前元素比栈顶小，就弹出栈顶，我们会得到一个底小顶大的单调栈，这就保证了「对于栈顶来说，左边（栈顶倒数第二个数）比栈顶小」。

遍历结束后，因为栈是严格递增的，所以栈中每个非零数字都需要操作一次。

代码实现时，可以直接把 nums 当作栈。
*/

	public int minOperations1(int[] nums) {
		int ans = 0;
		int top = -1; // 栈顶下标（把 nums 当作栈）
		for (int x : nums) {
			while (top >= 0 && x < nums[top]) {
				top--; // 出栈
				ans++;
			}
			// 如果 x 与栈顶相同，那么 x 与栈顶可以在同一次操作中都变成 0，x 无需入栈
			if (top < 0 || x != nums[top]) {
				nums[++top] = x; // 入栈
			}
		}
		return ans + top + (nums[0] > 0 ? 1 : 0);
	}


	//通过在单调栈里预先放一个0，可以直接省去判断0和空栈的语句
	public int minOperations2(int[] nums) {
		int ans = 0;
		List<Integer> list = new ArrayList<>();
		list.add(0); // 哨兵

		for(int a : nums){
			while(list.get(list.size()-1) > a)
				list.remove(list.size()-1);
			if(a != list.get(list.size()-1)){
				++ans;
				list.add(a);
			}
		}
		return ans;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
